#include<iostream>
#include<vector>

using namespace std;

 
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
 
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

    if (list1 == nullptr)
    {
        return list2;
    }
    else if (list2 == nullptr)
    {
        return list1;
    }
    ListNode* list1N = list1->next;
    ListNode* cur = list2;

    if (list1->val > list2->val)
    {
        while (cur)
        {
            if (cur->next == nullptr)
            {
                cur->next = list1;
                return list2;
            }
            else {
                if (list1->val <= cur->next->val)
                {
                    ListNode* curN = cur->next;
                    cur->next = list1;
                    list1->next = curN;
                    break;
                }

            }
            cur = cur->next;
        }

    }
else {
        list1->next = list2;
        list2 = list1;
        }
        return mergeTwoLists(list1N, list2);
}
    
    

int main()
{
    ListNode n1(1);
    ListNode n2(2);
    ListNode n3(4);

    ListNode n4(1);
    ListNode n5(3);
    ListNode n6(4);

    n1.next = &n2;
    n2.next = &n3;

    n4.next = &n5;
    n5.next = &n6;


    mergeTwoLists(&n1, &n4);


	return 0;
}